import java.util.ArrayList;
import java.util.List;

//计算右侧小于当前元素的个数
//https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

public class Test {
    public static void main(String[] args) {
        //
    }
}

class Solution {
    //需要的准备
    int[] ret;//返回（存储题目要求的值）
    int[] index;//存储下标（标记nums中当前元素的原始下标）
    //↓↓↓下边这两个其实都用于排序
    int[] tmpIndex;//用于下标更新
    int[] tmpNums;//用于更新（排序）
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        tmpIndex = new int[n];
        tmpNums = new int[n];

        //易忘：初始化index数组
        for(int i = 0; i < n; i++){
            index[i] = i;
        }

        func1(nums,0,n-1);

        for(int x : ret){
            list.add(x);
        }
        return list;
    }

    private void func1(int[] nums, int l, int r) {
        //[l,r]——要处理的区间
        if(l>=r) return;

        //将数组划分为两部分
        int mid = (l+r)/2;
        //[l,mid] [mid+1,r]
        func1(nums,l,mid);
        func1(nums,mid+1,r);

        //一左一右的情况
        int cur1 = l;
        int cur2 = mid+1;
        int i = 0;
        while(cur1<=mid && cur2<=r){
            //
            if(nums[cur1]<=nums[cur2]){
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }else{
                ret[index[cur1]] += r-cur2+1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }

        //
        while(cur1<=mid){
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while(cur2<=r){
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        //
        for(int j = l;j<=r;j++){
            nums[j] =  tmpNums[j-l];
            index[j] = tmpIndex[j-l];
        }


    }
}